package dipl.algorithm.utility.data;

import java.util.NoSuchElementException;

/**
 * Class represents a simple LIFO-data-structure - a stack.
 * It supports the typical stack-operations (push, pop and top).
 *
 * @author Marko Walther
 * @param <C> class of keys
 */
public class Stack<C> {

	//
	// TYPES
	//

	/**
	 * Class represents one stack-element containing a key
	 */
	protected class Item {
		/**
		 * key contained in item
		 */
		C key;
		/**
		 * next item
		 */
		Item next;
		/**
		 * Constructs new item with given key
		 * @param key key of item
		 */
		public Item( C key ) {
			this.key = key;
			next = null;
		}
	}

	//
	// MEMBERS
	//

	/**
	 * stack top element
	 */
	protected Item top;
	/**
	 * number of keys in stack
	 */
	protected int count;

	//
	// CONSTRUCTOR METHODS
	//

	/**
	 * Constructs new empty stack
	 */
	public Stack() {
		top = null;
		count = 0;
	}

	//
	// PUBLIC METHODS
	//

	/**
	 * Adds given item to stack and make it the new top.
	 * @param item item to add (item must be non-<code>null</code>)
	 */
	public void push( C item ) {
		if( item == null )
			throw new NullPointerException();
		Item i = new Item( item );
		if( top == null )
			top = i;
		else {
			i.next = top;
			top = i;
		}
		count++;
	}
	
	/**
	 * @return top-element from stack and removes it.
	 * If stack is empty a <code>NoSuchElementException</code> is thrown.
	 */
	public C pop() {
		if( top != null ) {
			C key = top.key;
			top = top.next;
			count--;
			return key;
		}
		throw new NoSuchElementException();
	}

	/**
	 * @return top-element from stack without removing it.
	 * If stack is empty a <code>NoSuchElementException</code> is thrown.
	 */
	public C top() {
		if( top != null )
			return top.key;
		throw new NoSuchElementException();
	}

	public int count() {
		return count;
	}

	public boolean insert( C item ) {
		push( item );
		return true;
	}
}
